package com.clps.algorithm.chapter07.二叉树每层的最大值;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 输入一棵二叉树，请找出二叉树中每一层的最大值。例如输入图7.4中的二叉树，返回三层节点的最大值[3, 4, 9]。
 */
public class demo01 {

    public static void main(String[] args) {

    }

    public List<Integer> largestValues(TreeNode root){
        int current = 0;
        int next = 0;

        Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null){
            queue.offer(root);
            current = 1;
        }

        List<Integer> result = new LinkedList<>();

        int max= Integer.MIN_VALUE;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            current--;
            max = Math.max(max,node.val);

            if(node.left!=null){
                queue.offer(node.left);
                next++;
            }

            if(current ==0){
                result.add(max);
                max = Integer.MIN_VALUE;
                current = next;
                next = 0;
            }
        }
        return  result;
    }

}
